import org.apache.poi.openxml4j.util.ZipSecureFile.ThresholdInputStream;

public class MaxSum {
	public static int maxSumRec(int[] a, int left, int right) {
		if (left == right) {
			if (a[left] > 0) {
				return a[left];
			} else {
				return 0;
			}
		}

		int center = (left + right) / 2;
		int maxLeftSum = maxSumRec(a, left, center);
		int maxRightSum = maxSumRec(a, center + 1, right);

		int maxLeftBorderSum = 0, lefBorderSum = 0;
		for (int i = center; i >= left; i--) {
			lefBorderSum += a[i];
			if (lefBorderSum > maxLeftBorderSum) {
				maxLeftBorderSum = lefBorderSum;
			}
		}

		int maxRightBorderSum = 0, rightBorderSum = 0;
		for (int i = center + 1; i <= right; i++) {
			rightBorderSum += a[i];
			if (maxRightBorderSum < rightBorderSum) {
				maxRightBorderSum = rightBorderSum;
			}
		}
		// return max3(maxLeftSum);
		return 0;
	}

	public static int maxSubSum4(int[] a) {
		int maxSum = 0, thisSum = 0;
		for (int i = 0; i < a.length; i++) {
			thisSum +=a[i];
			if(thisSum>maxSum){
				maxSum = thisSum;
			}else if(thisSum<=0){
				thisSum=0;
			}
		}
		return maxSum;
	}
}
